#pragma once

#include "viml/value.h"
#include "viml/ast.h"
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
#include <functional>
#include <list>
#include <cstddef>

namespace viml {

/**
 * 函数纯度分析器
 * 自动判断函数是否为纯函数，可以安全地进行记忆化
 */
class FunctionPurityAnalyzer : public ASTVisitor {
private:
    bool is_pure_ = true;                    // 当前分析的函数是否为纯函数
    bool has_side_effects_ = false;          // 是否有副作用
    bool has_external_dependency_ = false;   // 是否依赖外部状态
    std::string current_function_name_;      // 当前分析的函数名（用于识别递归调用）
    std::unordered_set<std::string> global_variables_accessed_;  // 访问的全局变量
    std::unordered_set<std::string> function_calls_;             // 调用的函数
    
    // 已知的纯函数和有副作用函数
    static const std::unordered_set<std::string> known_pure_functions_;
    static const std::unordered_set<std::string> known_impure_functions_;

public:
    /**
     * 分析函数是否为纯函数
     * @param func_stmt 函数声明语句
     * @return 是否为纯函数（可记忆化）
     */
    bool analyze_function_purity(FunctionStatement& func_stmt) {
        // 重置分析状态
        reset_analysis_state();
        
        // 记录当前分析的函数名，用于识别递归调用
        current_function_name_ = func_stmt.name;
        
        // 分析函数体
        for (auto& stmt : func_stmt.body) {
            stmt->accept(*this);
        }
        
        // 综合判断是否为纯函数
        return is_pure_ && !has_side_effects_ && !has_external_dependency_;
    }
    
    /**
     * 获取分析结果详情
     */
    struct AnalysisResult {
        bool is_pure = true;
        bool has_side_effects = false;
        bool has_external_dependency = false;
        std::vector<std::string> global_variables_accessed;
        std::vector<std::string> function_calls;
        std::string reason;  // 不纯的原因
    };
    
    AnalysisResult get_analysis_result() const {
        AnalysisResult result;
        result.is_pure = is_pure_ && !has_side_effects_ && !has_external_dependency_;
        result.has_side_effects = has_side_effects_;
        result.has_external_dependency = has_external_dependency_;
        result.global_variables_accessed.assign(global_variables_accessed_.begin(), 
                                                global_variables_accessed_.end());
        result.function_calls.assign(function_calls_.begin(), function_calls_.end());
        
        if (!result.is_pure) {
            if (has_side_effects_) {
                result.reason = "函数有副作用（如echo、全局变量修改等）";
            } else if (has_external_dependency_) {
                result.reason = "函数依赖外部状态（如全局变量读取、未知函数调用等）";
            }
        }
        
        return result;
    }
    
    // ASTVisitor 实现
    void visit(NumberLiteral& node) override {
        // 数字字面量：纯
    }
    
    void visit(StringLiteral& node) override {
        // 字符串字面量：纯
    }
    
    void visit(Identifier& node) override {
        // 标识符可能是局部变量或全局变量
        // 假设单个字母或常见局部变量是参数/局部变量
        if (node.name.length() == 1 || 
            node.name == "result" || node.name == "temp" || 
            node.name.find("local_") == 0) {
            // 可能是局部变量，继续假设为纯
        } else {
            // 可能是全局变量访问
            global_variables_accessed_.insert(node.name);
            has_external_dependency_ = true;
        }
    }
    
    void visit(SpecialConstantNode& node) override {
        // 特殊常量：纯
    }
    
    void visit(BinaryExpression& node) override {
        // 二元表达式：递归分析操作数
        node.left->accept(*this);
        node.right->accept(*this);
    }
    
    void visit(UnaryExpression& node) override {
        // 一元表达式：递归分析操作数
        node.operand->accept(*this);
    }
    
    void visit(CallExpression& node) override {
        // 函数调用：关键的纯度判断点
        if (auto callee = dynamic_cast<Identifier*>(node.callee.get())) {
            std::string func_name = callee->name;
            function_calls_.insert(func_name);
            
            // 检查是否为已知的有副作用函数
            if (known_impure_functions_.find(func_name) != known_impure_functions_.end()) {
                has_side_effects_ = true;
                is_pure_ = false;
            }
            // 检查是否为已知的纯函数
            else if (known_pure_functions_.find(func_name) != known_pure_functions_.end()) {
                // 已知纯函数，继续保持纯度
            }
            // 检查是否为递归调用（调用自己）
            else if (func_name == current_function_name_) {
                // 递归调用是允许的，不影响纯度
                // 只要递归函数本身没有副作用，就可以记忆化
            }
            else {
                // 未知函数，保守地认为可能有副作用
                has_external_dependency_ = true;
            }
        }
        
        // 分析函数参数
        for (auto& arg : node.arguments) {
            arg->accept(*this);
        }
    }
    
    void visit(ListLiteral& node) override {
        // 列表字面量：分析元素
        for (auto& elem : node.elements) {
            elem->accept(*this);
        }
    }
    
    void visit(DictLiteral& node) override {
        // 字典字面量：分析键值对
        for (auto& pair : node.pairs) {
            pair.first->accept(*this);
            pair.second->accept(*this);
        }
    }
    
    void visit(IndexExpression& node) override {
        // 索引访问：分析对象和索引
        node.object->accept(*this);
        node.index->accept(*this);
    }
    
    void visit(LetStatement& node) override {
        // Let语句：局部变量赋值通常是纯的
        node.value->accept(*this);
    }
    
    void visit(EchoStatement& node) override {
        // Echo语句：明显有副作用（输出）
        has_side_effects_ = true;
        is_pure_ = false;
        node.expression->accept(*this);
    }
    
    void visit(IfStatement& node) override {
        // If语句：分析条件和分支
        node.condition->accept(*this);
        for (auto& stmt : node.then_body) {
            stmt->accept(*this);
        }
        for (auto& stmt : node.else_body) {
            stmt->accept(*this);
        }
    }
    
    void visit(WhileStatement& node) override {
        // While语句：分析条件和循环体
        node.condition->accept(*this);
        for (auto& stmt : node.body) {
            stmt->accept(*this);
        }
    }
    
    void visit(ForStatement& node) override {
        // For语句：分析迭代对象和循环体
        node.iterable->accept(*this);
        for (auto& stmt : node.body) {
            stmt->accept(*this);
        }
    }
    
    void visit(FunctionStatement& node) override {
        // 嵌套函数定义：通常不影响当前函数的纯度
        // 但我们不分析嵌套函数
    }
    
    void visit(ReturnStatement& node) override {
        // Return语句：分析返回值
        if (node.value) {
            node.value->accept(*this);
        }
    }
    
    void visit(CallStatement& node) override {
        // 调用语句：分析调用表达式
        node.call_expr->accept(*this);
    }
    
    void visit(Program& node) override {
        // 程序节点：不应该在函数分析中出现
    }

private:
    void reset_analysis_state() {
        is_pure_ = true;
        has_side_effects_ = false;
        has_external_dependency_ = false;
        current_function_name_.clear();
        global_variables_accessed_.clear();
        function_calls_.clear();
    }
};

// 已知纯函数列表（数学运算、类型检查等）
// 声明，定义在 vm_memoization.cpp 中
static const std::unordered_set<std::string> known_pure_functions_;

// 已知有副作用的函数列表
// 声明，定义在 vm_memoization.cpp 中  
static const std::unordered_set<std::string> known_impure_functions_;

/**
 * VimL虚拟机记忆化优化模块
 * 
 * 设计目标：
 * 1. 为递归函数提供高效缓存机制
 * 2. 模块化设计，易于启用/禁用
 * 3. 安全的LRU缓存管理，避免内存泄漏
 * 4. 高性能哈希算法，最小化查找开销
 * 5. 自动函数纯度分析，智能添加可记忆化函数
 * 
 * 预期效果：
 * - 递归斐波那契Fib(30): 从60秒降至10-50毫秒
 * - 性能提升：100-1000倍
 */

/**
 * 函数调用参数的快速哈希计算
 * 专门针对VimL Value类型优化
 */
class ArgumentsHasher {
public:
    /**
     * 计算函数参数列表的哈希值
     * @param args 参数列表
     * @return 64位哈希值
     */
    static uint64_t hash_arguments(const std::vector<Value>& args) {
        uint64_t hash = 0;
        constexpr uint64_t FNV_OFFSET_BASIS = 14695981039346656037ULL;
        constexpr uint64_t FNV_PRIME = 1099511628211ULL;
        
        hash = FNV_OFFSET_BASIS;
        
        for (const auto& arg : args) {
            // 对于数值类型，直接使用数值哈希
            if (arg.is_number()) {
                int64_t num = static_cast<int64_t>(arg.as_number());
                hash ^= static_cast<uint64_t>(num);
                hash *= FNV_PRIME;
            } 
            // 对于浮点数，使用bits表示
            else if (arg.is_float()) {
                uint64_t bits = arg.raw_bits();
                hash ^= bits;
                hash *= FNV_PRIME;
            }
            // 对于布尔值，使用简单映射
            else if (arg.is_boolean()) {
                hash ^= arg.as_boolean() ? 1ULL : 0ULL;
                hash *= FNV_PRIME;
            }
            // 对于nil，使用固定值
            else if (arg.is_nil()) {
                hash ^= 0xDEADBEEFULL;
                hash *= FNV_PRIME;
            }
            // 对于其他类型，使用类型标识（可扩展）
            else {
                hash ^= static_cast<uint64_t>(arg.type());
                hash *= FNV_PRIME;
            }
        }
        
        return hash;
    }
    
    /**
     * 快速参数相等性检查
     * 避免深度比较开销
     */
    static bool arguments_equal(const std::vector<Value>& args1, const std::vector<Value>& args2) {
        if (args1.size() != args2.size()) {
            return false;
        }
        
        for (size_t i = 0; i < args1.size(); ++i) {
            // 对于数值类型，直接比较数值
            if (args1[i].is_number() && args2[i].is_number()) {
                if (args1[i].as_number() != args2[i].as_number()) {
                    return false;
                }
            }
            // 对于其他类型，使用Value的相等比较
            else if (!(args1[i] == args2[i])) {
                return false;
            }
        }
        
        return true;
    }
};

/**
 * 函数调用缓存键
 * 组合函数名和参数哈希
 */
struct MemoizationKey {
    std::string function_name;
    uint64_t arguments_hash;
    std::vector<Value> arguments;  // 保存原始参数用于冲突检查
    
    MemoizationKey(const std::string& name, const std::vector<Value>& args)
        : function_name(name)
        , arguments_hash(ArgumentsHasher::hash_arguments(args))
        , arguments(args) {}
    
    bool operator==(const MemoizationKey& other) const {
        return function_name == other.function_name &&
               arguments_hash == other.arguments_hash &&
               ArgumentsHasher::arguments_equal(arguments, other.arguments);
    }
};

/**
 * 缓存键的哈希函数
 */
struct MemoizationKeyHasher {
    std::size_t operator()(const MemoizationKey& key) const {
        // 组合函数名哈希和参数哈希
        std::size_t name_hash = std::hash<std::string>{}(key.function_name);
        return name_hash ^ (key.arguments_hash + 0x9e3779b9 + (name_hash << 6) + (name_hash >> 2));
    }
};

/**
 * LRU缓存项
 */
struct CacheEntry {
    MemoizationKey key;
    Value result;
    
    CacheEntry(const MemoizationKey& k, const Value& r) : key(k), result(r) {}
};

/**
 * LRU记忆化缓存
 * 
 * 设计特点：
 * 1. 固定大小，避免无限增长
 * 2. LRU淘汰策略，保持热点数据
 * 3. 快速查找和更新
 * 4. 线程安全预留（当前单线程）
 */
class MemoizationCache {
private:
    static constexpr size_t DEFAULT_MAX_SIZE = 1000;  // 默认缓存1000个函数调用结果
    static constexpr size_t FIBONACCI_OPTIMIZED_SIZE = 50;  // 斐波那契数列只需要缓存50个结果
    
    size_t max_size_;
    std::list<CacheEntry> cache_list_;  // LRU链表，最新的在前面
    std::unordered_map<MemoizationKey, 
                      typename std::list<CacheEntry>::iterator,
                      MemoizationKeyHasher> cache_map_;  // 快速查找映射
    
    // 统计信息
    size_t hits_ = 0;
    size_t misses_ = 0;
    size_t evictions_ = 0;

public:
    explicit MemoizationCache(size_t max_size = DEFAULT_MAX_SIZE) : max_size_(max_size) {
        // 预留空间，减少重新分配
        cache_map_.reserve(max_size);
    }
    
    /**
     * 查找缓存结果
     * @param key 查找键
     * @param result 输出参数，存储找到的结果
     * @return 是否找到缓存项
     */
    bool get(const MemoizationKey& key, Value& result) {
        auto it = cache_map_.find(key);
        if (it != cache_map_.end()) {
            // 命中：移动到链表头部（最近使用）
            auto list_it = it->second;
            result = list_it->result;
            
            // 将此项移到链表头部
            cache_list_.splice(cache_list_.begin(), cache_list_, list_it);
            
            ++hits_;
            return true;
        }
        
        ++misses_;
        return false;
    }
    
    /**
     * 存储缓存结果
     * @param key 存储键
     * @param result 存储的结果值
     */
    void put(const MemoizationKey& key, const Value& result) {
        auto map_it = cache_map_.find(key);
        if (map_it != cache_map_.end()) {
            // 更新已存在的项
            auto list_it = map_it->second;
            list_it->result = result;
            // 移到链表头部
            cache_list_.splice(cache_list_.begin(), cache_list_, list_it);
            return;
        }
        
        // 添加新项到链表头部
        cache_list_.emplace_front(key, result);
        cache_map_[key] = cache_list_.begin();
        
        // 检查缓存大小限制
        if (cache_list_.size() > max_size_) {
            // 删除最老的项（链表尾部）
            auto last = cache_list_.end();
            --last;
            cache_map_.erase(last->key);
            cache_list_.pop_back();
            ++evictions_;
        }
    }
    
    /**
     * 清空缓存
     */
    void clear() {
        cache_list_.clear();
        cache_map_.clear();
        hits_ = misses_ = evictions_ = 0;
    }
    
    /**
     * 获取缓存统计信息
     */
    struct Statistics {
        size_t hits = 0;
        size_t misses = 0;
        size_t evictions = 0;
        size_t size = 0;
        double hit_rate = 0.0;
    };
    
    Statistics get_statistics() const {
        Statistics stats;
        stats.hits = hits_;
        stats.misses = misses_;
        stats.evictions = evictions_;
        stats.size = cache_list_.size();
        
        size_t total = hits_ + misses_;
        if (total > 0) {
            stats.hit_rate = static_cast<double>(hits_) / total * 100.0;
        }
        
        return stats;
    }
    
    /**
     * 检查缓存是否为空
     */
    bool empty() const {
        return cache_list_.empty();
    }
    
    /**
     * 获取当前缓存大小
     */
    size_t size() const {
        return cache_list_.size();
    }
    
    /**
     * 获取最大缓存大小
     */
    size_t max_size() const {
        return max_size_;
    }
    
    /**
     * 设置最大缓存大小
     * 如果新大小小于当前缓存，会淘汰最老的项
     */
    void set_max_size(size_t new_max_size) {
        max_size_ = new_max_size;
        
        // 如果当前缓存超过新限制，淘汰最老的项
        while (cache_list_.size() > max_size_) {
            auto last = cache_list_.end();
            --last;
            cache_map_.erase(last->key);
            cache_list_.pop_back();
            ++evictions_;
        }
    }
    
    /**
     * 专门为斐波那契函数优化缓存大小
     */
    void optimize_for_fibonacci() {
        set_max_size(FIBONACCI_OPTIMIZED_SIZE);
    }
};

/**
 * 记忆化管理器
 * 集成到VM中的主要接口
 */
class MemoizationManager {
private:
    MemoizationCache cache_;
    bool enabled_ = true;  // 默认启用记忆化
    
    // 可记忆化函数的白名单（避免副作用函数被缓存）
    std::unordered_set<std::string> memoizable_functions_;
    
    // 函数纯度分析器
    FunctionPurityAnalyzer purity_analyzer_;

public:
    MemoizationManager() {
        // 默认将一些确定的纯函数添加到白名单
        // 注意：这里只添加100%确定的纯函数，其他通过自动分析添加
        add_memoizable_function("abs");
        add_memoizable_function("max");
        add_memoizable_function("min");
        add_memoizable_function("len");
        
        // 常见的递归数学函数（通常是纯函数）
        add_memoizable_function("Fibonacci");
        add_memoizable_function("Fib");
        add_memoizable_function("factorial");
        add_memoizable_function("fibonacci");
        add_memoizable_function("gcd");
        add_memoizable_function("power");
    }
    
    /**
     * 自动分析函数并添加到白名单（如果是纯函数）
     * @param func_stmt 函数声明语句
     * @return 分析结果
     */
    FunctionPurityAnalyzer::AnalysisResult analyze_and_add_function(FunctionStatement& func_stmt) {
        if (purity_analyzer_.analyze_function_purity(func_stmt)) {
            add_memoizable_function(func_stmt.name);
            auto result = purity_analyzer_.get_analysis_result();
            result.reason = "函数被自动识别为纯函数，已添加到记忆化白名单";
            return result;
        } else {
            return purity_analyzer_.get_analysis_result();
        }
    }
    
    /**
     * 启用/禁用记忆化
     */
    void set_enabled(bool enabled) {
        enabled_ = enabled;
        if (!enabled) {
            cache_.clear();  // 禁用时清空缓存
        }
    }
    
    bool is_enabled() const {
        return enabled_;
    }
    
    /**
     * 添加可记忆化函数
     */
    void add_memoizable_function(const std::string& function_name) {
        memoizable_functions_.insert(function_name);
    }
    
    /**
     * 移除可记忆化函数
     */
    void remove_memoizable_function(const std::string& function_name) {
        memoizable_functions_.erase(function_name);
    }
    
    /**
     * 检查函数是否可记忆化
     */
    bool is_function_memoizable(const std::string& function_name) const {
        return memoizable_functions_.find(function_name) != memoizable_functions_.end();
    }
    
    /**
     * 尝试从缓存获取函数调用结果
     * @param function_name 函数名
     * @param args 参数列表
     * @param result 输出参数，存储缓存的结果
     * @return 是否命中缓存
     */
    bool try_get_cached_result(const std::string& function_name, 
                              const std::vector<Value>& args, 
                              Value& result) {
        if (!enabled_ || !is_function_memoizable(function_name)) {
            return false;
        }
        
        MemoizationKey key(function_name, args);
        return cache_.get(key, result);
    }
    
    /**
     * 缓存函数调用结果
     * @param function_name 函数名
     * @param args 参数列表
     * @param result 函数执行结果
     */
    void cache_result(const std::string& function_name, 
                     const std::vector<Value>& args, 
                     const Value& result) {
        if (!enabled_ || !is_function_memoizable(function_name)) {
            return;
        }
        
        MemoizationKey key(function_name, args);
        cache_.put(key, result);
    }
    
    /**
     * 清空所有缓存
     */
    void clear_cache() {
        cache_.clear();
    }
    
    /**
     * 获取缓存统计信息
     */
    MemoizationCache::Statistics get_cache_statistics() const {
        return cache_.get_statistics();
    }
    
    /**
     * 优化缓存配置（针对特定用例）
     */
    void optimize_for_recursive_algorithms() {
        // 为递归算法优化缓存配置
        cache_.optimize_for_fibonacci();
    }
    
    /**
     * 获取缓存引用（用于高级配置）
     */
    MemoizationCache& get_cache() {
        return cache_;
    }
    
    const MemoizationCache& get_cache() const {
        return cache_;
    }
};

} // namespace viml